package com.future;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * Description: 264. 丑数 II
 *
 * @author weiruibai.vendor
 * Date: 2022/9/13 16:11
 */
public class Solution_264_II {

    public static void main(String[] args) {
        int times = 1000;
        System.out.println(nthUglyNumber(times));
        /*for (int i = 1; i < times; i++) {
            if (nthUglyNumber(i) != nthUglyNumber_v2(i)) {
                throw new RuntimeException("err:i=" + i);
            }
            System.out.println("进度：" + i);
        }
        System.out.println("GOOD!");*/
    }

    /**
     * 超时
     *
     * @param n
     * @return
     */
    public static int nthUglyNumber_v2(int n) {
        if (n < 1) {
            return 0;
        }
        List<Integer> factory = new ArrayList<Integer>() {{
            add(1);
            add(2);
            add(3);
            add(5);
        }};
        Set<Integer> set = new HashSet<>();
        set.add(1);
        int ans = 1;
        for (int i = 2; set.size() < n; i++) {
            int num = i;
            for (int k = 0; k < factory.size(); k++) {
                if (factory.get(k) == 1) {
                    continue;
                }
                while (num % factory.get(k) == 0) {
                    num = num / factory.get(k);
                }
                if (factory.contains(num)) {
                    set.add(i);
                    ans = i;
                    break;
                }
            }
        }
        return ans;
    }

    /**
     * @param n
     * @return
     */
    public static int nthUglyNumber(int n) {
        int ugly = 1;
        Set<Long> set = new HashSet<>();
        set.add((long) ugly);
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.offer((long) ugly);
        int[] factory = {2, 3, 5};
        for (int i = 0; i < n; i++) {
            long poll = queue.poll();
            ugly = (int) poll;
            for (int j = 0; j < factory.length; j++) {
                long res = factory[j] * poll;
                if (set.add(res)) {
                    queue.offer(res);
                }
            }
        }
        return ugly;
    }
}
